package com.huawei.M01.iterator;

import java.util.Arrays;

/**
 * 根据前序遍历和后序遍历构造一个shu
 *
 * @author 111
 */


public class ConstructFromPrePost {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        int length = postorder.length;
        if (length == 0) {
            return null;
        }
        // 构造一个树，根节点为前序遍历的第0个值
        TreeNode root = new TreeNode(preorder[0]);
        if (length == 1) {
            return root;
        }

        int indexOfLeftRoot = 0;
        // 遍历找到左分支的根节点
        for (int i = 0; i < length; i++) {
            if (preorder[1] == postorder[i]) {
                indexOfLeftRoot = i + 1;
                break;
            }
        }

        // 根据找到到左分支根节点索引值进行重构树
        root.left = constructFromPrePost(
                Arrays.copyOfRange(preorder, 1, indexOfLeftRoot + 1),
                Arrays.copyOfRange(postorder, 0, indexOfLeftRoot)
        );
        root.right = constructFromPrePost(
                Arrays.copyOfRange(preorder, indexOfLeftRoot + 1, length),
                Arrays.copyOfRange(postorder, indexOfLeftRoot, length - 1)
        );
        return root;
    }
}
